1. Field of the Invention
The present invention relates to a small size decoder reducing power consumption and more particularly to a series reed-Solomon decoder synchronized with a bit clock signal.
2. Description of the Related Arts
In typical digital communication systems, the Reed-Solomon decoder has been used for correcting an error generated in signal transmission. For example, the Reed-Solomon decoder has been recently used in the digital video broadcasting.
The Reed-Solomon decoder decodes the coded data on block-by-block basis in order to correct an error. The encoding on block-by-block basis is to divide the input sequential data into a plurality of block of a predetermined length, to code the data by blocks and to add a dummy byte to the end of the coded block data. While this coding on block-by-block basis can correct the transmission errors by adding the dummy byte to it at a decoding part, the dummy byte added to the transmission data causes the channel width to be wider. However, this encoding and decoding on block-by-block basis have been widely used in the data error correction because of the excellent correction ability for the continuous data errors.
FIGS. 1A to 1D are schematic views illustrating conventional encoding and decoding on block-by-block basis. This block encoding data used in the reed-Solomon encoding/decoding apparatus consists of 188 bytes and 16 dummy byte (hereinafter, referred to as check bytes). Accordingly, this invention will describe the block data of 204 bytes as an exemplary.
Referring to FIG. 1A, a source encoding data is divided by unit blocks (188 bytes) before a channel encoding. The channel encoding data has the size of 204 bytes by adding the divided data (188 bytes) to the check byte of 16 bytes, as shown in FIG. 1B. With the encoding on block-by-block basis, the channel extends to 204 bytes from 188 bytes.
Generally, the Reed-Solomon encoding/decoding method carries out the modular operations on the Galore field. The block data M(x) is written according to the procedure as follows: EQU M(x)M.sub.187 X.sup.187 +M.sub.186 X.sup.186 + . . . +M.sub.2 X.sup.2 +M.sub.1 X.sup.1 +M.sub.0 X.sup.0 (1)
As shown above Equation 1, the block data is expressed as a polynomial M(x) consisting of specific order related to each byte. That is, the data divided into a plurality of blocks of "order+1". The channel data is obtained by multiplying the lock data M(x) by a 16-order creation polynomial G(x). That is, the 203-order channel encoding data C(x) is obtained by multiplying the 187-order block data by the 16-order creation polynomial, where the coefficients of the block data M(x) are the same as those of the 203-order to 16-order channel encoding data C(x) and the coefficients of the 15-order channel encoding data C(x) and the coefficients of the 15-order to 0-order channel encoding data C(x) relate to the check bytes. By using these check byte, the errors generated in transferring data can be corrected. The channel encoding data C(x) and the creation polynomial G(x) are expressed as follows: ##EQU1##
The channel encoding data C(x) is transferred to a decoder in the receiving terminal through a transmission channel with a noise. Therefore, the data input into the decoder of the receiving terminal is a receiving data R(x) which is different from the channel encoding data C(x). The receiving data R(x) is expressed as follows: ##EQU2##
As shown in FIG. 1B, the receiving data R(x) may include the error data E(x) and the error data E(x) has random values. As mentioned above, the coding data, to which the check byte of 16 bytes is added, may generally corrects 8 byte errors.
Referring to FIG. 2, the Reed-Solomon decoder for correcting 8 bytes in the erroneous receiving data R(x) will be described. First, the Reed-Solomon decoder includes: a register 21 temporally storing the block data input through the transmission channel until the error values are calculated; a syndrome calculation part 22 for calculating the polynomial to determine whether or not there is an error in the received block data; an error position and estimation polynomial calculation part 23 for determining coefficients of the error position polynomial from the syndrome polynomial of the syndrome calculation part 22 using the Euclid algorithm, thereby calculating the error positions and the estimated polynomial; a error position polynomial root and error value calculation part 24 for calculating roots of the calculated error position polynomial from the error position and estimation polynomial calculation part 23 and then calculating the error values; a control signal generating part 26 for controlling the syndrome calculation part 22, the error position and estimation polynomial calculation part 23 and the error position polynomial root and error value calculation part 24; and an adder 25 for adding the block data stored in the register 21 to the result of the error position polynomial root and error value calculation part 24.
To calculate the error positions and error values form received block data R(x), the syndrome polynomial S(x) having this information should be calculated and the syndrome polynomial S(x) is written as follow: ##EQU3## where S.sub.k is a coefficient value of the syndrome polynomial S(x) and .alpha. is a value on the Galore field.
The syndrome polynomial S(x) is composed of 16 coefficients which are the same as the number of the check bytes. That is, the syndrome polynomial S(x) is a 16-order polynomial. The coefficients of the syndrome polynomial S(x) are calculated by blocks so that only one syndrome polynomial S(x) is calculated in only one block data. Therefore, the syndrome calculation part 22 has a latency of 204 bytes, which is a delay time from input to output, and its throughout is 204 bytes.
The Syndrome calculation part 22 obtained by Equation 4 is input into the error position and estimation polynomial calculation part 23 so that an error position polynomial .sigma.(x) and an error value polynomial .omega.(x) capable of inferring error positions and values are calculated using the Euclid algorithm. The Euclid algorithm can be described mathematically as follows: EQU R.sub.0 (x)=A(x), Q.sub.0 (x)=S(x), .lambda..sub.0 (x)=0, .mu..sub.0 (x)=1 EQU R.sub.i (x)=[.sigma..sub.i-1 b.sub.i-1 R.sub.i-1 (x)+.sigma..sub.i-1 a.sub.i-1 Q.sub.i-1 (x)] -x.sup.{l.sbsp.i-1.sup.} [.sigma..sub.i-1 a.sub.i-1 Q.sub.i-1(x) +.sigma.b.sub.i-1 R.sub.i-1 (x)] EQU .lambda..sub.i (x)=[.sigma..sub.i-1 b.sub.i-1 .lambda..sub.i-1 (x)+.sigma..sub.i-1 a.sub.i-1 .mu..sub.i-1 (x)] -x.sup.{l.sbsp.i-1.sup.} [.sigma..sub.i-1 a.sigma..sub.i-1 .mu..sub.i-1 (x)+.sigma.b.sub.i-1 .lambda..sub.i-1 (x)] EQU Q.sub.i-1 (x)=[.sigma..sub.i-1 Q.sub.i-1 (x)+.sigma..sub.i-1 R.sub.i-1 (x)] EQU .mu..sub.i (x)=[.sigma..sub.i-1 .mu..sub.i-1 (x)+.sigma..sub.i-1 .lambda..sub.i-1 (x)] EQU l.sub.i-1 =deg(R.sub.i-1 (x))-deg(Q.sub.i-1 (x)) EQU .sigma..sub.i-1 =1, if l.sub.i-1 .gtoreq.0 EQU .sigma..sub.i-1 =0, if l.sub.i-1 &lt;0 (5)
where R.sub.0 (x) is a reference polynomial which is given within itself, Q.sub.0 (x) is a correction syndrome polynomial which is an input of the syndrome polynomial, .lambda..sub.0 (x) is a reference polynomial and .mu..sub.0 (x) is a deletion pointer polynomial.
The final aim of the Euclid algorithm is to determine the error position polynomial and the error value polynomial. The error position and estimation polynomial calculation part 23 is terminated when the order of the reference polynomial R.sub.0 (x) used in the Euclid algorithm is below 8.
In case where there is an error in byte within the block from the error position polynomial and the error value polynomial, the algorithm to eliminate the error is the search algorithm of Chien. In other words, it is determined whether or not there exists an error, by substituting a root corresponding to each byte for the variable in the error position polynomial and the error value polynomial, which are calculated by the Euclid algorithm. If an error exists in it, the value of the error is calculated by the following equation 6: ##EQU4##
Typically, the input data of the Reed-Solomon decoder is input on block-by-block basis in response to the byte clock. Therefore, in embodying this Reed-Solomon decoder, its operation is carried out by the byte clock. As a result, the conventional Reed-Solomon decoder causes each calculation part to have separate cells, thereby increasing the size of decoder.